
<!DOCTYPE html>

<html lang="zh">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Part A: 决策树 &#8212; Datawhale</title>
    
  <link href="../_static/css/theme.css" rel="stylesheet" />
  <link href="../_static/css/index.c5995385ac14fb8791e8eb36b4908be2.css" rel="stylesheet" />

    
  <link rel="stylesheet"
    href="../_static/vendor/fontawesome/5.13.0/css/all.min.css">
  <link rel="preload" as="font" type="font/woff2" crossorigin
    href="../_static/vendor/fontawesome/5.13.0/webfonts/fa-solid-900.woff2">
  <link rel="preload" as="font" type="font/woff2" crossorigin
    href="../_static/vendor/fontawesome/5.13.0/webfonts/fa-brands-400.woff2">

    
      

    
    <link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
    <link rel="stylesheet" href="../_static/sphinx-book-theme.5f77b4aec8189eecf79907ce328c390d.css" type="text/css" />
    <link rel="stylesheet" type="text/css" href="../_static/togglebutton.css" />
    <link rel="stylesheet" type="text/css" href="../_static/mystnb.css" />
    
  <link rel="preload" as="script" href="../_static/js/index.1c5a1a01449ed65a7b51.js">

    <script id="documentation_options" data-url_root="../" src="../_static/documentation_options.js"></script>
    <script src="../_static/jquery.js"></script>
    <script src="../_static/underscore.js"></script>
    <script src="../_static/doctools.js"></script>
    <script src="../_static/togglebutton.js"></script>
    <script >var togglebuttonSelector = '.toggle, .admonition.dropdown, .tag_hide_input div.cell_input, .tag_hide-input div.cell_input, .tag_hide_output div.cell_output, .tag_hide-output div.cell_output, .tag_hide_cell.cell, .tag_hide-cell.cell';</script>
    <script src="../_static/sphinx-book-theme.12a9622fbb08dcb3a2a40b2c02b83a57.js"></script>
    <script async="async" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.7/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
    <script type="text/x-mathjax-config">MathJax.Hub.Config({"tex2jax": {"inlineMath": [["\\(", "\\)"]], "displayMath": [["\\[", "\\]"]], "processRefs": false, "processEnvironments": false}})</script>
    <link rel="shortcut icon" href="../_static/favicon.ico"/>
    <link rel="index" title="索引" href="../genindex.html" />
    <link rel="search" title="搜索" href="../search.html" />
    <link rel="next" title="Part B: 集成模式" href="02_ensemble.html" />
    <link rel="prev" title="树模型与集成学习" href="index.html" />
    <meta name="viewport" content="width=device-width, initial-scale=1" />
    <meta name="docsearch:language" content="en" />
    
  </head>
  <body data-spy="scroll" data-target="#bd-toc-nav" data-offset="80">
    
    <div class="container-fluid" id="banner"></div>

    

    <div class="container-xl">
      <div class="row">
          
<div class="col-12 col-md-3 bd-sidebar site-navigation show" id="site-navigation">
    
        <div class="navbar-brand-box">
    <a class="navbar-brand text-wrap" href="../index.html">
      
      <img src="../_static/logo.png" class="logo" alt="logo">
      
      
      <h1 class="site-logo" id="site-title">Datawhale</h1>
      
    </a>
</div><form class="bd-search d-flex align-items-center" action="../search.html" method="get">
  <i class="icon fas fa-search"></i>
  <input type="search" class="form-control" name="q" id="search-input" placeholder="Search the docs ..." aria-label="Search the docs ..." autocomplete="off" >
</form><nav class="bd-links" id="bd-docs-nav" aria-label="Main navigation">
    <div class="bd-toc-item active">
        <ul class="current nav bd-sidenav">
 <li class="toctree-l1 current active has-children">
  <a class="reference internal" href="index.html">
   树模型与集成学习
  </a>
  <input checked="" class="toctree-checkbox" id="toctree-checkbox-1" name="toctree-checkbox-1" type="checkbox"/>
  <label for="toctree-checkbox-1">
   <i class="fas fa-chevron-down">
   </i>
  </label>
  <ul class="current">
   <li class="toctree-l2 current active">
    <a class="current reference internal" href="#">
     Part A: 决策树
    </a>
   </li>
   <li class="toctree-l2">
    <a class="reference internal" href="02_ensemble.html">
     Part B: 集成模式
    </a>
   </li>
   <li class="toctree-l2">
    <a class="reference internal" href="03_ada.html">
     Part C: 自适应提升法
    </a>
   </li>
   <li class="toctree-l2">
    <a class="reference internal" href="04_gbdt.html">
     Part D: 梯度提升树
    </a>
   </li>
  </ul>
 </li>
 <li class="toctree-l1 has-children">
  <a class="reference internal" href="../02_em_sampling/index.html">
   EM算法与抽样理论
  </a>
  <input class="toctree-checkbox" id="toctree-checkbox-2" name="toctree-checkbox-2" type="checkbox"/>
  <label for="toctree-checkbox-2">
   <i class="fas fa-chevron-down">
   </i>
  </label>
  <ul>
   <li class="toctree-l2">
    <a class="reference internal" href="../02_em_sampling/01_em.html">
     EM算法
    </a>
   </li>
   <li class="toctree-l2">
    <a class="reference internal" href="../02_em_sampling/02_sample.html">
     抽样理论
    </a>
   </li>
  </ul>
 </li>
</ul>

    </div>
</nav> <!-- To handle the deprecated key -->

<div class="navbar_extra_footer">
  Theme by the <a href="https://ebp.jupyterbook.org">Executable Book Project</a>
</div>

</div>


          


          
<main class="col py-md-3 pl-md-4 bd-content overflow-auto" role="main">
    
    <div class="topbar container-xl fixed-top">
    <div class="topbar-contents row">
        <div class="col-12 col-md-3 bd-topbar-whitespace site-navigation show"></div>
        <div class="col pl-md-4 topbar-main">
            
            <button id="navbar-toggler" class="navbar-toggler ml-0" type="button" data-toggle="collapse"
                data-toggle="tooltip" data-placement="bottom" data-target=".site-navigation" aria-controls="navbar-menu"
                aria-expanded="true" aria-label="Toggle navigation" aria-controls="site-navigation"
                title="Toggle navigation" data-toggle="tooltip" data-placement="left">
                <i class="fas fa-bars"></i>
                <i class="fas fa-arrow-left"></i>
                <i class="fas fa-arrow-up"></i>
            </button>
            
            
<div class="dropdown-buttons-trigger">
    <button id="dropdown-buttons-trigger" class="btn btn-secondary topbarbtn" aria-label="Download this page"><i
            class="fas fa-download"></i></button>

    <div class="dropdown-buttons">
        <!-- ipynb file if we had a myst markdown file -->
        
        <!-- Download raw file -->
        <a class="dropdown-buttons" href="../_sources/01_tree_ensemble/01_tree.md.txt"><button type="button"
                class="btn btn-secondary topbarbtn" title="Download source file" data-toggle="tooltip"
                data-placement="left">.md</button></a>
        <!-- Download PDF via print -->
        <button type="button" id="download-print" class="btn btn-secondary topbarbtn" title="Print to PDF"
            onClick="window.print()" data-toggle="tooltip" data-placement="left">.pdf</button>
    </div>
</div>

            <!-- Source interaction buttons -->

            <!-- Full screen (wrap in <a> to have style consistency -->

<a class="full-screen-button"><button type="button" class="btn btn-secondary topbarbtn" data-toggle="tooltip"
        data-placement="bottom" onclick="toggleFullScreen()" aria-label="Fullscreen mode"
        title="Fullscreen mode"><i
            class="fas fa-expand"></i></button></a>

            <!-- Launch buttons -->

        </div>

        <!-- Table of contents -->
        <div class="d-none d-md-block col-md-2 bd-toc show">
            
            <div class="tocsection onthispage pt-5 pb-3">
                <i class="fas fa-list"></i> Contents
            </div>
            <nav id="bd-toc-nav">
                <ul class="visible nav section-nav flex-column">
 <li class="toc-h2 nav-item toc-entry">
  <a class="reference internal nav-link" href="#id1">
   1. 信息论基础
  </a>
 </li>
 <li class="toc-h2 nav-item toc-entry">
  <a class="reference internal nav-link" href="#id2">
   2. 分类树的节点分裂
  </a>
 </li>
 <li class="toc-h2 nav-item toc-entry">
  <a class="reference internal nav-link" href="#cart">
   3. CART树
  </a>
 </li>
 <li class="toc-h2 nav-item toc-entry">
  <a class="reference internal nav-link" href="#id3">
   4. 决策树的剪枝
  </a>
 </li>
 <li class="toc-h2 nav-item toc-entry">
  <a class="reference internal nav-link" href="#id4">
   知识回顾
  </a>
 </li>
</ul>

            </nav>
        </div>
    </div>
</div>
    <div id="main-content" class="row">
        <div class="col-12 col-md-9 pl-md-3 pr-md-0">
        
              <div>
                
  <div class="section" id="part-a">
<h1>Part A: 决策树<a class="headerlink" href="#part-a" title="永久链接至标题">¶</a></h1>
<div class="section" id="id1">
<h2>1. 信息论基础<a class="headerlink" href="#id1" title="永久链接至标题">¶</a></h2>
<p>树具有天然的分支结构。对于分类问题而言，决策树的思想是用节点代表样本集合，通过某些判定条件来对节点内的样本进行分配，将它们划分到该节点下的子节点，并且要求各个子节点中类别的纯度之和应高于该节点中的类别纯度，从而起到分类效果。</p>
<p>节点纯度反映的是节点样本标签的不确定性。当一个节点的纯度较低时，说明每种类别都倾向于以比较均匀的频率出现，从而我们较难在这个节点上得到关于样本标签的具体信息，其不确定性较高。当一个节点的纯度很高时，说明有些类别倾向于以比较高的频率出现，从而我们能够更有信心地把握这个节点样本标签的具体信息，即确定性较高。</p>
<p>那对于给定在<span class="math notranslate nohighlight">\(n\)</span>个状态上定义的离散分布<span class="math notranslate nohighlight">\(\textbf{p}=[p_1,...,p_n]^T\)</span>，如何定义度量不确定性的函数<span class="math notranslate nohighlight">\(H(\textbf{p})\)</span>，即<span class="math notranslate nohighlight">\(H(p_1,...,p_n)\)</span>呢？香农（1916-2001）于1948年，在创造信息论的著名论文<a class="reference external" href="https://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf">《A Mathematical Theory of Communication》</a>中指出如下定理：</p>
<div class="admonition-appendix-2 admonition">
<p class="admonition-title">定理（证明见论文的Appendix 2）</p>
<p>若度量不确定性的函数<span class="math notranslate nohighlight">\(H\)</span>满足三个信息熵条件，则<span class="math notranslate nohighlight">\(H\)</span>的形式只能是</p>
<div class="math notranslate nohighlight">
\[
H(p_1,...,p_n)=-C\sum_{i=1}^np_i\log p_i
\]</div>
<p>其中，信息熵条件如下：</p>
<ul class="simple">
<li><p><span class="math notranslate nohighlight">\(H\)</span>是关于<span class="math notranslate nohighlight">\(p_i\)</span>的连续函数。</p></li>
<li><p>若<span class="math notranslate nohighlight">\(p_1=...=p_n\)</span>，则<span class="math notranslate nohighlight">\(H\)</span>关于<span class="math notranslate nohighlight">\(n\)</span>单调递增。</p></li>
<li><p>若将某一个<span class="math notranslate nohighlight">\(p_i\)</span>拆分为<span class="math notranslate nohighlight">\(p_{i1}\)</span>和<span class="math notranslate nohighlight">\(p_{i2}\)</span>，即<span class="math notranslate nohighlight">\(p_{i1}+p_{i2}=p_i\)</span>，则</p></li>
</ul>
<div class="math notranslate nohighlight">
\[
H(p_1,...,p_{i-1},p_{i+1},...,p_n,p_{i1},p_{i2})=H(p_1,...,p_n)+p_iH(\frac{p_{i1}}{p_i}, \frac{p_{i2}}{p_i})
\]</div>
</div>
<p>从构造和计算的角度而言，条件一是容易满足的。对于条件二而言，假设原来箱子里分别有10个球和100个球，加入每次摸到的球都是等概率抽出的，那么100个球的箱子产生的不确定性必然是要大于10个球的箱子产生的不确定性，即<span class="math notranslate nohighlight">\(H\)</span>在等概率条件下关于<span class="math notranslate nohighlight">\(n\)</span>递增。</p>
<p>条件三看上去比较复杂，但其意义是容易理解的，即<span class="math notranslate nohighlight">\(n\)</span>个事件拆分为<span class="math notranslate nohighlight">\(n+1\)</span>个事件时的不确定性增加了，并且增加的不确定性与拆分时的比例和拆分事件的概率有关。举例来说：将<span class="math notranslate nohighlight">\(\textbf{p}=[0.9,0.1]\)</span>分别拆分为<span class="math notranslate nohighlight">\(\textbf{p}_1=[0.45,0.45,0.1]\)</span>和<span class="math notranslate nohighlight">\(\textbf{p}_2=[0.9,0.05,0.05]\)</span>，那么显然<span class="math notranslate nohighlight">\(\textbf{p}_1\)</span>增加的不确定性远超过<span class="math notranslate nohighlight">\(\textbf{p}_2\)</span>；同时，将<span class="math notranslate nohighlight">\(\textbf{p}=[0.9,0.1]\)</span>分别拆分为<span class="math notranslate nohighlight">\(\textbf{p}_3=[0.8,0.1,0.1]\)</span>，那么显然<span class="math notranslate nohighlight">\(\textbf{p}_1\)</span>增加的不确定性也远超过<span class="math notranslate nohighlight">\(\textbf{p}_3\)</span>。</p>
<p>由于指标<span class="math notranslate nohighlight">\(H(\textbf{p})\)</span>中的自变量<span class="math notranslate nohighlight">\(\textbf{p}\)</span>是对于某个随机变量<span class="math notranslate nohighlight">\(Y\)</span>分布的描述，因此不妨将其记为信息熵<span class="math notranslate nohighlight">\(H(Y)\)</span>来反映<span class="math notranslate nohighlight">\(Y\)</span>的不确定性。对于定义在有限状态集合<span class="math notranslate nohighlight">\(\{y_1,...,y_K\}\)</span>上的离散变量而言，对应信息熵的最大值在离散均匀分布时取到，最小值在单点分布时取到。此时，离散信息熵为</p>
<div class="math notranslate nohighlight">
\[
H(Y)=-\sum_{k=1}^K p(y_k)\log_2p(y_k)
\]</div>
<p>首先，我们需要定义当<span class="math notranslate nohighlight">\(p=0\)</span>时<span class="math notranslate nohighlight">\(p\log_2p\triangleq 0\)</span>，原因在于</p>
<div class="math notranslate nohighlight">
\[
\lim \limits_{p\to 0^+} p \log{p} = \lim \limits_{p \to 0^+} \frac{\log p}{1/p} = \lim \limits_{p \to 0^+} \frac{1/p}{-1/p^2}=\lim \limits_{p \to 0^+} -p = 0
\]</div>
<p>离散熵的极值问题是带有约束的极值问题，记<span class="math notranslate nohighlight">\(p_k=P(Y=y_k)\)</span>和<span class="math notranslate nohighlight">\(\mathbf{p}=[p_1,...,p_K]^T\)</span>，则约束条件为<span class="math notranslate nohighlight">\(\mathbb{1}^T\mathbf{p}=1\)</span>，拉格朗日函数为</p>
<div class="math notranslate nohighlight">
\[
L(\mathbf{p})=-\mathbf{p}^T\log \mathbf{p} + \lambda (\mathbb{1}^T\mathbf{p}-1)
\]</div>
<p>求偏导数后可解得<span class="math notranslate nohighlight">\(\mathbf{p}^*=[\frac{1}{K},...,\frac{1}{K}]^T\)</span>，此时<span class="math notranslate nohighlight">\(H(Y)=-\mathbb{E}_{Y}\log_2p(Y)=\log K\)</span>。</p>
<div class="admonition- admonition">
<p class="admonition-title">补充材料</p>
<p>有关向量求导的内容可参考<a class="reference external" href="https://en.wikipedia.org/wiki/Matrix_calculus">这个wiki页面</a>中的描述。</p>
</div>
<p>对于离散随机变量<span class="math notranslate nohighlight">\(X\)</span>，由于<span class="math notranslate nohighlight">\(p(Y)\in [0,1]\)</span>，故<span class="math notranslate nohighlight">\(-\log_2p(Y)\geq 0\)</span>，从而<span class="math notranslate nohighlight">\(\mathbb{E}_{Y}[-\log_2p(Y)]\geq 0\)</span>。注意到对于<span class="math notranslate nohighlight">\(\forall k\in \{1,...,K\}\)</span>，当<span class="math notranslate nohighlight">\(p_k=1\)</span>，即<span class="math notranslate nohighlight">\(p_{k'}=0(k'\in \{1,...,K\}/k)\)</span>时，<span class="math notranslate nohighlight">\(H(Y)=0\)</span>。因此，离散信息熵的最小值为0且在单点分布时取到。由于<span class="math notranslate nohighlight">\(\mathbf{p}^*\)</span>是极值问题的唯一解，因此离散熵的最大值为<span class="math notranslate nohighlight">\(\log K\)</span>且在离散均匀分布时取到。</p>
<p>在决策树的分裂过程中，我们不但需要考察本节点的不确定性或纯度，而且还要考察子节点的平均不确定性或平均纯度来决定是否进行分裂。子节点的产生来源于决策树分支的条件，因此我们不但要研究随机变量的信息熵，还要研究在给定条件下随机变量的平均信息熵或条件熵（Conditional Entropy）。从名字上看，条件熵就是条件分布的不确定性，那么自然可以如下定义条件熵<span class="math notranslate nohighlight">\(H(Y\vert X)\)</span>为</p>
<div class="math notranslate nohighlight">
\[
\mathbb{E}_{X}[\mathbb{E}_{Y\vert X}[-\log_2p(Y\vert X)]]
\]</div>
<p>对于离散条件熵，设随机变量<span class="math notranslate nohighlight">\(X\)</span>所有可能的取值为<span class="math notranslate nohighlight">\(\{x_1,...,x_M\}\)</span>，上式可展开为</p>
<div class="math notranslate nohighlight">
\[
-\sum_{m=1}^Mp(x_m)\sum_{k=1}^K p(y_k\vert X=x_m)\log_2p(y_k\vert X=x_m)
\]</div>
<p>有了信息熵和条件熵的基础，我们就能很自然地定义信息增益（Information Gain），即节点分裂之后带来了多少不确定性的降低或纯度的提高。在得到了随机变量<span class="math notranslate nohighlight">\(X\)</span>的取值信息时，随机变量<span class="math notranslate nohighlight">\(Y\)</span>不确定性的平均减少量为</p>
<div class="math notranslate nohighlight">
\[
G(Y,X)=H(Y)-H(Y\vert X)
\]</div>
<p>从直觉上说，随机变量<span class="math notranslate nohighlight">\(Y\)</span>关于<span class="math notranslate nohighlight">\(X\)</span>的信息增益一定是非负的，因为我们额外地知道了随机变量<span class="math notranslate nohighlight">\(X\)</span>的取值，这个条件降低了<span class="math notranslate nohighlight">\(Y\)</span>的不确定性。下面我们就从数学角度来证明其正确性。</p>
<div class="admonition- admonition">
<p class="admonition-title">定理</p>
<p>设<span class="math notranslate nohighlight">\(Y\)</span>和<span class="math notranslate nohighlight">\(X\)</span>为离散随机变量，<span class="math notranslate nohighlight">\(Y\)</span>关于<span class="math notranslate nohighlight">\(X\)</span>的信息增益<span class="math notranslate nohighlight">\(G(Y,X)\)</span>非负。</p>
</div>
<div class="admonition- admonition">
<p class="admonition-title">证明</p>
<p>由信息增益的定义得：</p>
<div class="math notranslate nohighlight">
\[\begin{split}
\begin{aligned}
G(Y,X)&amp;=\mathbb{E}_{Y}[-\log_2p(Y)]-\mathbb{E}_{X}[\mathbb{E}_{Y\vert X}[-\log_2p(Y\vert X)]]\\
&amp;=-\sum_{k=1}^Kp(y_k)\log_2p(y_k)+\sum_{m=1}^Mp(x_m)\sum_{k=1}^K p(y_k\vert X=x_m)\log_2p(y_k\vert X=x_m) \\
&amp;=-\sum_{k=1}^K[\sum_{m=1}^Mp(y_k, x_m)]\log_2p(y_k)+\sum_{k=1}^K\sum_{m=1}^M p(x_m)\frac{p(y_k, x_m)}{p(x_m)}\log_2\frac{p(y_k, x_m)}{p(x_m)}\\
&amp;=\sum_{k=1}^K\sum_{m=1}^Mp(y_k,x_m)[\log_2\frac{p(y_k, x_m)}{p(x_m)}-\log_2p(y_k)] \\
&amp;=-\sum_{k=1}^K\sum_{m=1}^M p(y_k,x_m) \log_2\frac{p(y_k)p(x_m)}{p(y_k, x_m)}
\end{aligned}
\end{split}\]</div>
<p>从上式可以发现，信息增益<span class="math notranslate nohighlight">\(G(Y,X)\)</span>在本质上就是<span class="math notranslate nohighlight">\(p(y,x)\)</span>关于<span class="math notranslate nohighlight">\(p(y)p(x)\)</span>的KL散度，而KL散度的非负性由Jensen不等式可得：</p>
<div class="math notranslate nohighlight">
\[\begin{split}
\begin{aligned}
G(Y,X)&amp;\geq -\log_2 [\sum_{k=1}^K\sum_{m=1}^M p(y_k,x_m)\frac{p(y_k)p(x_m)}{p(y_k, x_m)}]\\
&amp;= -\log_2 [\sum_{k=1}^K\sum_{m=1}^Mp(y_k,x_m)] = 0
\end{aligned}
\end{split}\]</div>
</div>
<div class="margin sidebar">
<p class="sidebar-title"></p>
<p>【练习】定义<span class="math notranslate nohighlight">\(X,Y\)</span>的联合熵为<span class="math notranslate nohighlight">\(H(Y,X)\)</span>为<span class="math notranslate nohighlight">\(\mathbb{E}_{(Y,X)\sim p(y,x)}[-\log_2p(Y,X)]\)</span></p>
<ul class="simple">
<li><p>请证明如下关系：
<span class="math notranslate nohighlight">\(\tiny G(Y,X)=H(X)-H(X\vert Y)\)</span>
<span class="math notranslate nohighlight">\(\tiny G(Y,X)=H(X)+H(Y)-H(Y,X)\)</span>
<span class="math notranslate nohighlight">\(\tiny G(Y,X)=H(Y,X)-H(X\vert Y)-H(Y\vert X)\)</span></p></li>
<li><p>下图被分为了A、B和C三个区域。若AB区域代表X的不确定性，BC区域代表Y的不确定性，那么<span class="math notranslate nohighlight">\(H(X)\)</span>、<span class="math notranslate nohighlight">\(H(Y)\)</span>、<span class="math notranslate nohighlight">\(H(X\vert Y)\)</span>、<span class="math notranslate nohighlight">\(H(Y\vert X)\)</span>、<span class="math notranslate nohighlight">\(H(Y,X)\)</span>和<span class="math notranslate nohighlight">\(G(Y,X)\)</span>分别指代的是哪片区域？</p></li>
</ul>
<div class="figure align-center">
<a class="reference internal image-reference" href="../_images/tree_pic3.png"><img alt="../_images/tree_pic3.png" src="../_images/tree_pic3.png" style="width: 180px;" /></a>
</div>
</div>
<p>上述证明中的Jensen不等式的取等条件为<span class="math notranslate nohighlight">\(p(y,x)=p(y)p(x)\)</span>，其实际意义为随机变量<span class="math notranslate nohighlight">\(Y\)</span>和<span class="math notranslate nohighlight">\(X\)</span>独立。这个条件同样与直觉相符合，因为如果<span class="math notranslate nohighlight">\(Y\)</span>和<span class="math notranslate nohighlight">\(X\)</span>独立，那么意味着我们无论是否知道<span class="math notranslate nohighlight">\(X\)</span>的信息，都不会对<span class="math notranslate nohighlight">\(Y\)</span>的不确定性产生影响，此时信息增益为0。</p>
<p>用信息增益的大小来进行决策树的节点分裂时，由于真实的分布函数未知，故用<span class="math notranslate nohighlight">\(p(y)\)</span>和<span class="math notranslate nohighlight">\(p(y\vert x)\)</span>的经验分布（即频率）来进行概率的估计。若节点<span class="math notranslate nohighlight">\(N\)</span>每个分支下的样本数量为<span class="math notranslate nohighlight">\(D_1,...,D_M\)</span>，记<span class="math notranslate nohighlight">\(\tilde{p}(x_m)=\frac{D_m}{\sum_{m'=1}^M D_{m'}}(m\in\{1,...,M\})\)</span>，<span class="math notranslate nohighlight">\(\tilde{p}(y_k)\)</span>和<span class="math notranslate nohighlight">\(\tilde{p}(y_k\vert x_m)\)</span>分别为节点中第k个类别的样本占节点总样本的比例和第m个子节点中第k个类别的样本数量占该子节点总样本的比例，则节点<span class="math notranslate nohighlight">\(N\)</span>分裂的信息增益定义为</p>
<div class="math notranslate nohighlight">
\[
G_N(Y,X)=-\sum_{i=1}^K\tilde{p}(y_k)\log_2 \tilde{p}(y_k)+\sum_{m=1}^M\tilde{p}(x_m)\sum_{k=1}^K\tilde{p}(y_k\vert x_m)\log_2 \tilde{p}(y_k\vert x_m)
\]</div>
</div>
<div class="section" id="id2">
<h2>2. 分类树的节点分裂<a class="headerlink" href="#id2" title="永久链接至标题">¶</a></h2>
<p>对于每个节点进行分裂决策时，我们会抽出max_features个特征进行遍历以比较信息增益的大小。特征的类别可以分为三种情况讨论：类别特征、数值特征和含缺失值的特征，它们各自的处理方法略有不同。</p>
<p>对于类别特征而言，给定一个阈值<span class="math notranslate nohighlight">\(\epsilon\)</span>，树的每一个节点会选择最大信息增益<span class="math notranslate nohighlight">\(G^{max}_N(Y,X)\)</span>对应的特征进行分裂，直到所有节点的相对最大信息增益<span class="math notranslate nohighlight">\(\frac{D_N}{D_{all}}G^{max}_N(Y,X)\)</span>小于<span class="math notranslate nohighlight">\(\epsilon\)</span>，<span class="math notranslate nohighlight">\(D_N\)</span>和<span class="math notranslate nohighlight">\(D_{all}\)</span>分别指节点<span class="math notranslate nohighlight">\(N\)</span>的样本个数和整个数据集的样本个数，这种生成算法称为ID3算法。在sklearn中，<span class="math notranslate nohighlight">\(\epsilon\)</span>即为min_impurity_decrease。</p>
<p>C4.5算法在ID3算法的基础上做出了诸多改进，包括但不限于：处理数值特征、处理含缺失值的特征、使用信息增益比代替信息增益以及给出树的剪枝策略。其中，剪枝策略将在第4节进行讲解，下面先对前3个改进的细节来进行介绍。</p>
<p>在处理节点数值特征时，可以用两种方法来将数值特征通过分割转化为类别，它们分别是最佳分割法和随机分割法，分别对应了sklearn中splitter参数的best选项和random选项。</p>
<div class="margin sidebar">
<p class="sidebar-title"></p>
<p>【练习】假设当前我们需要处理一个分类问题，请问对输入特征进行归一化会对树模型的类别输出产生影响吗？请解释原因。</p>
</div>
<p>随机分割法下，取<span class="math notranslate nohighlight">\(s\sim U[x_{min}, x_{max}]\)</span>，其中<span class="math notranslate nohighlight">\(U[x_{min}, x_{max}]\)</span>代表特征最小值和最大值范围上的均匀分布，将节点样本按照特征<span class="math notranslate nohighlight">\(\mathbf{x}\)</span>中的元素是否超过<span class="math notranslate nohighlight">\(s\)</span>把样本划分为两个集合，这等价于把数值变量转换为了类别变量。此时，根据这两个类别来计算树节点分裂的信息增益，并将它作为这个数值特征分裂的信息增益。</p>
<p>最佳分割法下，依次令<span class="math notranslate nohighlight">\(s\)</span>取遍所有的<span class="math notranslate nohighlight">\(x_i(i=1,...,D_N)\)</span>，将其作为分割点，按照特征<span class="math notranslate nohighlight">\(\mathbf{x}\)</span>中的元素是否超过<span class="math notranslate nohighlight">\(s\)</span>把样本划分为两个集合，计算所有<span class="math notranslate nohighlight">\(s\)</span>对应信息增益的最大值，并将其作为这个数值特征分裂的信息增益。</p>
<div class="margin sidebar">
<p class="sidebar-title"></p>
<p>【练习】如果将系数替换为<span class="math notranslate nohighlight">\(1-\gamma^2\)</span>，请问对缺失值是加强了还是削弱了惩罚？</p>
</div>
<p>C4.5算法处理缺失数据的思想非常简单，样本的缺失值占比越大，那么对信息增益的惩罚就越大，这是因为缺失值本身就是一种不确定性成分。设节点<span class="math notranslate nohighlight">\(N\)</span>的样本缺失值比例为<span class="math notranslate nohighlight">\(\gamma\)</span>，记非缺失值对应的类别标签和特征分别为<span class="math notranslate nohighlight">\(\tilde{Y}\)</span>和<span class="math notranslate nohighlight">\(\tilde{X}\)</span>，则修正的信息增益为</p>
<div class="math notranslate nohighlight">
\[
\tilde{G}(Y,X) = (1-\gamma)G(\tilde{Y},\tilde{X})
\]</div>
<p>当数据完全缺失时<span class="math notranslate nohighlight">\(\gamma=1\)</span>，信息增益为0；当数据没有缺失值时<span class="math notranslate nohighlight">\(\gamma=0\)</span>，信息增益与原来的值保持一致。</p>
<p>在C4.5算法中，使用了信息增益比来代替信息增益，其原因在于信息增益来选择的决策树对类别较多的特征具有天然的倾向性，例如当某一个特征<span class="math notranslate nohighlight">\(X\)</span>（身份证号码、学号等）的类别数恰好就是样本数量时，此时由于<span class="math notranslate nohighlight">\(H(Y\vert X)=0\)</span>，即<span class="math notranslate nohighlight">\(G(Y,X)\)</span>达到最大值，因此必然会优先选择此特征进行分裂，但这样的情况是非常不合理的。</p>
<p>我们在第1节已经证明了，在类别占比均匀的情况下，类别数越多则熵越高，因此我们可以使用特征对应的熵来进行惩罚，即熵越高的变量会在信息增益上赋予更大程度的抑制，由此我们可以定义信息增益比为</p>
<div class="math notranslate nohighlight">
\[
G^R(Y,X) = \frac{G(Y,X)}{H(X)}
\]</div>
<p>在前面的部分中，我们讨论了单个节点如何选取特征进行分裂，但没有涉及到树节点的分裂顺序。例如下图所示，假设当前已经处理完了节点2的分裂，所有黄色节点（包括2号节点）都是当前已经存在的树节点，那么我们接下来究竟应该选取叶节点3号、4号和5号中的哪一个节点来继续进行决策以生成新的叶节点6号和7号？</p>
<div class="figure align-center">
<a class="reference internal image-reference" href="../_images/tree_pic1.png"><img alt="../_images/tree_pic1.png" src="../_images/tree_pic1.png" style="width: 400px;" /></a>
</div>
<p>在sklearn中提供了两种生长模式，它们分别被称为深度优先生长和最佳增益生长，当参数max_leaf_nodes使用默认值None时使用前者，当它被赋予某个数值时使用后者。</p>
<div class="margin sidebar">
<p class="sidebar-title"></p>
<p>【练习】如果将树的生长策略从深度优先生长改为广度优先生长，假设其他参数保持不变的情况下，两个模型对应的结果输出可能不同吗？</p>
</div>
<p>深度优先生长采用深度优先搜索的方法：若当前节点存在未搜索过的子节点，则当前节点跳转到子节点进行分裂决策；若当前节点为叶节点，则调转到上一层节点，直到根节点不存在未搜索过的子节点为止。对上图而言，当前节点为2号，它的两个子节点4号和5号都没有被搜索过，因此下一步则选择两个节点中的一个进行跳转。当决策树使用最佳增益生长时，每次总是选择会带来最大相对信息增益的节点进行分裂，直到叶节点的最大数量达到max_left_nodes。</p>
</div>
<div class="section" id="cart">
<h2>3. CART树<a class="headerlink" href="#cart" title="永久链接至标题">¶</a></h2>
<p>CART（Classification And Regression Tree）是一棵二叉树，它既能处理分类问题，又能够处理回归问题。值得注意的是，在sklearn中并没有实现处理类别特征和处理缺失值的功能，前者是因为多个类别的特征会产生多叉树，后者是因为sklearn认为用户应当自己决定缺失值的处理而不是交给模型来决定。</p>
<p>对于回归树而言，每个叶节点输出的不再是类别而是数值，其输出值为该叶节点所有样本标签值的均值。在每次分裂时，我们希望不同的子节点之间的差异较大，但每个子节点内部的差异较小。此时，分割策略仍然可以采用随机分割法或最佳分割法，只是现在不再以熵（条件熵）来评价节点（子节点）的纯度。</p>
<p>我们应当如何定义回归树的节点纯度？对于数值标签而言，我们可以认为节点间元素大小越接近则纯度越高，因此可以考虑使用均方误差（MSE）或平均绝对误差（MAE）来替换熵和条件熵的位置。</p>
<p>设节点<span class="math notranslate nohighlight">\(N\)</span>的样本标签为<span class="math notranslate nohighlight">\(y^{(D)}_1,...,y^{(D)}_N\)</span>，左右子节点的样本个数分别为<span class="math notranslate nohighlight">\(y^{(L)}_1,...,y^{(L)}_{N_R}\)</span>和<span class="math notranslate nohighlight">\(y^{(R)}_1,...,y^{(R)}_{N_R}\)</span>，记<span class="math notranslate nohighlight">\(\bar{y}^{(D)}=\frac{1}{N}\sum_{i=1}^{N}y^{(D)}_i\)</span>、<span class="math notranslate nohighlight">\(\bar{y}^{(L)}=\frac{1}{N_L}\sum_{i=1}^{N_L}y^{(L)}_i\)</span>和<span class="math notranslate nohighlight">\(\bar{y}^{(R)}=\frac{1}{N_R}\sum_{i=1}^{N_R}y^{(R)}_i\)</span>分别为节点<span class="math notranslate nohighlight">\(N\)</span>的样本标签均值、左子节点的样本标签均值和右子节点的样本标签均值，再记<span class="math notranslate nohighlight">\(\tilde{y}^{(D)}\)</span>、<span class="math notranslate nohighlight">\(\tilde{y}^{(L)}\)</span>和<span class="math notranslate nohighlight">\(\tilde{y}^{(R)}\)</span>分别为节点<span class="math notranslate nohighlight">\(N\)</span>的样本标签中位数、左子节点的样本标签中位数和右子节点的样本标签中位数。</p>
<div class="margin sidebar">
<p class="sidebar-title"></p>
<p>【练习】在一般的机器学习问题中，我们总是通过一组参数来定义模型的损失函数，并且在训练集上以最小化该损失函数为目标进行优化。请问对于决策树而言，模型优化的目标是什么？</p>
</div>
<p>此时，两者的信息增益可以分别定义为</p>
<div class="math notranslate nohighlight">
\[
G^{MSE}(Y,X)=\frac{1}{N}\sum_{i=1}^{N}(y^{(D)}_i-\bar{y}^{(D)})^2-\frac{N_L}{N}\frac{1}{N_L}\sum_{i=1}^{N_L}(y^{(L)}_i-\bar{y}^{(L)})^2-\frac{N_R}{N}\frac{1}{N_R}\sum_{i=1}^{N_R}(y^{(R)}_i-\bar{y}^{(R)})^2
\]</div>
<div class="math notranslate nohighlight">
\[
G^{MAE}(Y,X)=\frac{1}{N}\sum_{i=1}^{N}\vert y^{(D)}_i-\tilde{y}^{(D)}\vert-\frac{N_L}{N}\frac{1}{N_L}\sum_{i=1}^{N_L}\vert y^{(L)}_i-\tilde{y}^{(L)}\vert-\frac{N_R}{N}\frac{1}{N_R}\sum_{i=1}^{N_R}\vert y^{(R)}_i-\tilde{y}^{(R)}\vert
\]</div>
<p>当处理分类问题时，虽然ID3或C4.5定义的熵仍然可以使用，但是由于对数函数<span class="math notranslate nohighlight">\(\log\)</span>的计算代价较大，CART将熵中的<span class="math notranslate nohighlight">\(\log\)</span>在<span class="math notranslate nohighlight">\(p=1\)</span>处利用一阶泰勒展开，基尼系数定义为熵的线性近似，即由于</p>
<div class="math notranslate nohighlight">
\[
H(Y)=\mathbb{E}_YI(p)=\mathbb{E}_Y[-\log_2p(Y)]\approx\mathbb{E}_Y[1-p(Y)]
\]</div>
<p>从而定义基尼系数为</p>
<div class="math notranslate nohighlight">
\[\begin{split}
\begin{aligned}
{\rm Gini}(Y)&amp;=\mathbb{E}_Y[1-p(Y)]\\
&amp;=\sum_{k=1}^K \tilde{p}(y_k)(1-\tilde{p}(y_k))\\
&amp;=1-\sum_{k=1}^K\tilde{p}^2(y_k)
\end{aligned}
\end{split}\]</div>
<div class="margin sidebar">
<p class="sidebar-title"></p>
<p>【练习】对信息熵中的<span class="math notranslate nohighlight">\(\log\)</span>函数在<span class="math notranslate nohighlight">\(p=1\)</span>处进行一阶泰勒展开可以近似为基尼系数，那么如果在<span class="math notranslate nohighlight">\(p=1\)</span>处进行二阶泰勒展开我们可以获得什么近似指标？请写出对应指标的信息增益公式。</p>
</div>
<p>类似地定义条件基尼系数为</p>
<div class="math notranslate nohighlight">
\[\begin{split}
\begin{aligned}
{\rm Gini}(Y\vert X)&amp;=\mathbb{E}_X[\mathbb{E}_{Y\vert X}[1-p(Y\vert X)]]\\
&amp;=\sum_{m=1}^M \tilde{p}(x_m)\sum_{k=1}^K[\tilde{p}(y_k\vert x_m)(1-\tilde{p}(y_k\vert x_m))]\\
&amp;=\sum_{m=1}^M \tilde{p}(x_m)[1-\sum_{k=1}^K\tilde{p}^2(y_k\vert x_m)]
\end{aligned}
\end{split}\]</div>
<div class="margin sidebar">
<p class="sidebar-title"></p>
<p>【练习】除了信息熵和基尼系数之外，我们还可以使用节点的<span class="math notranslate nohighlight">\(1-\max_{k}p(Y=y_k)\)</span>和第<span class="math notranslate nohighlight">\(m\)</span>个子节点的<span class="math notranslate nohighlight">\(1-\max_{k}p(Y=y_k\vert X=x_m)\)</span>来作为衡量纯度的指标。请解释其合理性并给出相应的信息增益公式。</p>
</div>
<p>从而引出基于基尼系数的信息增益为</p>
<div class="math notranslate nohighlight">
\[
G(Y,X)={\rm Gini}(Y)-{\rm Gini}(Y\vert X)
\]</div>
</div>
<div class="section" id="id3">
<h2>4. 决策树的剪枝<a class="headerlink" href="#id3" title="永久链接至标题">¶</a></h2>
<div class="margin sidebar">
<p class="sidebar-title"></p>
<p>【练习】为什么对没有重复特征值的数据，决策树能够做到损失为0？</p>
</div>
<p>决策树具有很强的拟合能力，对于任何一个没有特征重复值的数据集，决策树一定能够在训练集上做到分类错误率或均方回归损失为0，因此我们应当通过一些手段来限制树的生长，这些方法被称为决策树的剪枝方法。其中，预剪枝是指树在判断节点是否分裂的时候就预先通过一些规则来阻止其分裂，后剪枝是指在树的节点已经全部生长完成后，通过一些规则来摘除一些子树。</p>
<div class="margin sidebar">
<p class="sidebar-title"></p>
<p>【练习】如何理解min_samples_leaf参数能够控制回归树输出值的平滑程度？</p>
</div>
<p>在sklearn的CART实现中，一共有6个控制预剪枝策略的参数，它们分别是最大树深度max_depth、节点分裂的最小样本数min_samples_split、叶节点最小样本数min_samples_leaf、节点样本权重和与所有样本权重和之比的最小比例min_weight_fraction_leaf、最大叶节点总数max_leaf_nodes以及之前提到的分裂阈值min_impurity_decrease。</p>
<p>后剪枝过程又称作MCCP过程，即Minimal Cost-Complexity Pruning，它由参数ccp_alpha控制，记其值为<span class="math notranslate nohighlight">\(\alpha\)</span>。一般而言，树的叶子越多就越复杂，为了抑制树的生长，我们定义以节点<span class="math notranslate nohighlight">\(N\)</span>为根节点的树<span class="math notranslate nohighlight">\(T^N\)</span>的复杂度为该树的叶节点数量<span class="math notranslate nohighlight">\(\vert T^N\vert\)</span>。设树<span class="math notranslate nohighlight">\(T\)</span>的剪枝度量为</p>
<div class="math notranslate nohighlight">
\[
R_\alpha(T^N)=R(T^N)+\alpha\vert T^N\vert
\]</div>
<p>其中，<span class="math notranslate nohighlight">\(R(T^N)\)</span>代表各个叶子节点的平均不纯度，此处的不纯度即指分类中的信息熵或者回归中的均方误差或平均绝对误差，即MCCP中的Cost部分，<span class="math notranslate nohighlight">\(\alpha\vert T^N\vert\)</span>对应的就是Complexity部分。</p>
<p>对于树的单个节点而言，由于此时节点数为1，故其剪枝度量为<span class="math notranslate nohighlight">\(R_\alpha(Node^N)=R(Node^N)+\alpha\)</span>。树剪枝的思想在于，如果对于决策树某一个节点为根的子树，其根的剪枝度量低于该子树的剪枝度量，那么这个根节点就没有必要分裂，即砍掉这棵子树中除了根节点以外的所有节点。</p>
<p>此时，我们可以得到剪枝的依据为</p>
<div class="math notranslate nohighlight">
\[
R_{\alpha}(Node^N)\leq R_{\alpha}(T^N)
\]</div>
<p>这等价于</p>
<div class="math notranslate nohighlight">
\[
R(Node^N)+\alpha \leq R(T^N) + \alpha \vert T^N\vert
\]</div>
<p>对上式进行移项后可得</p>
<div class="math notranslate nohighlight">
\[
E(Node^N) = \frac{R(Node^N)-R(T)}{\vert T^N\vert -1}\leq \alpha
\]</div>
<p>这个条件表明只要<span class="math notranslate nohighlight">\(E(Node^N)\)</span>的值小于给定的参数cpp_alpha，那么这个节点下的所有节点都会被删除。事实上在sklearn中，在树完全生成后就会把所有节点的<span class="math notranslate nohighlight">\(E(Node^N)\)</span>值进行记录，每次剪枝都会分别查看所有非叶子节点的树节点对应的<span class="math notranslate nohighlight">\(E(Node^N)\)</span>值，并且对具有最小<span class="math notranslate nohighlight">\(E(Node^N)\)</span>值的非叶子节点进行剪枝，直到所有节点的<span class="math notranslate nohighlight">\(E(Node^N)\)</span>值都大于给定的cpp_alpha。</p>
</div>
<div class="section" id="id4">
<h2>知识回顾<a class="headerlink" href="#id4" title="永久链接至标题">¶</a></h2>
<ol class="simple">
<li><p>ID3树算法、C4.5树算法和CART算法之间有何异同？</p></li>
<li><p>什么是信息增益？它衡量了什么指标？它有什么缺陷？</p></li>
<li><p>sklearn决策树中的random_state参数控制了哪些步骤的随机性？</p></li>
<li><p>决策树如何处理连续变量和缺失变量？</p></li>
<li><p>基尼系数是什么？为什么要在CART中引入它？</p></li>
<li><p>什么是树的预剪枝和后剪枝？具体分别是如何操作的？</p></li>
</ol>
</div>
</div>


              </div>
              
        
        <div class='prev-next-bottom'>
            
    <a class='left-prev' id="prev-link" href="index.html" title="previous page">树模型与集成学习</a>
    <a class='right-next' id="next-link" href="02_ensemble.html" title="next page">Part B: 集成模式</a>

        </div>
        
        </div>
    </div>
    <footer class="footer mt-5 mt-md-0">
    <div class="container">
      <p>
        
          By GYH<br/>
        
            &copy; Copyright 2021, GYH.<br/>
      </p>
    </div>
  </footer>
</main>


      </div>
    </div>
  
  <script src="../_static/js/index.1c5a1a01449ed65a7b51.js"></script>

  
  </body>
</html>